// 01背包问题 
/**
 * 
 * @param {*} wight 
 * @param {*} value 
 * @param {*} size 
 * @returns 
 */
// 二维数组解法 i为下标0-i的物品编号 j为背包的最大容量
function testWeightBagProblem(wight,value,size){
    const len = wight.length, 
    dp = Array.from({length: len + 1}).map(
      () => Array(size + 1).fill(0)
    );//dp 初始化 设置为0 
  //遍历顺序：先遍历物品，再遍历背包容量 交换也可以
  for(let i = 1; i <= len; i++) {// 从1开始循环 
    for(let j = 0; j <= size; j++) {
      if(wight[i - 1] <= j) {// 如果当前背包可以继续添加
        // 最大的为前一个值加这次
        dp[i][j] = Math.max(
          dp[i - 1][j], 
          value[i - 1] + dp[i - 1][j - wight[i - 1]]
          // dp[i-1][j-weight[i-1]] 不放i时给i腾出位置时的价值
          //dp[i - 1][j - weight[i-1]] 为背包容量为j - weight[i-1]的时候不放物品i的最大价值
        )
      } else {// 否则当前价值不变
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[len][size];
}

/**
 * 
 * @param {*} weight 
 * @param {*} value 
 * @param {*} size 
 * @returns 
 */
// 一维数组解法
// 相当于省去了dp[i] i为物品的编号 j为背包的容量 
// dp[i - 1]那一层拷贝到dp[i]上 滚动数组
function testWeightBagProblem1(weight,value,size){
  let dp=new Array(size+1).fill(0);
  // 如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
  for(let i=1;i<=weight.length;i++){// 先遍历物品嵌套遍历背包容量
    for(let j=size;j>=weight[i-1];j--){// 得使用倒叙 保证物品i只被放入一次
      // 从后往前循环，每次取得状态不会和之前取得状态重合
      dp[j]=Math.max(dp[j-1],dp[j-weight[i-1]]+value[i-1])
      // 容量为 j - 物品i重量 的背包 加上 物品i的价值
    }
  }
  return dp[size];
}

function test () {
    console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
    console.log(testWeightBagProblem1([1, 3, 4, 5], [15, 20, 30, 55], 6));
  }
  
  test();

// 完全背包问题
